/* 343. 整数拆分 */
/**
 * @param {number} n
 * @return {number}
 */
/* 记忆化递归 */
var integerBreak = function (n) {
    const memo = new Array(n + 1)
    const dfs = (n) => {
        if (memo[n]) return memo[n]
        let res = 0
        /* 对于数字n 可以拆分成 i 和 n-i  i的范围从 1 到 n-1 */
        for (let i = 1; i <= n - 1; i++) {
            res = Math.max(res, i * (n - i), i * dfs(n - i))
        }
        return memo[n] = res;
    }
    return dfs(n)
};
/* 
    动态规划 
    dp[i] 表示正整数i拆分成的整数的最大乘积
*/
var integerBreak = function (n) {
    const dp = new Array(n + 1)
    dp[1] = 1
    dp[2] = 1
    for (let i = 3; i <= n; i++) {
        dp[i] = 0
        /* 对于数字 i ,它可以分为2份,j 和 i - j ,j的范围使1 ~  i- j */
        for (let j = 1; j <= i - j; j++) {
            /* 对于 i - j 这部分可以拆或不拆，不拆就是i-j,拆就是dp[i-j] */
            dp[i] = Math.max(dp[i], j * (i - j), j * dp[i - j])
        }
    }
    return dp[n]
}
/* 数学 */
var integerBreak = function (n) {
    if (n === 2) return 1
    if (n === 3) return 2
    let res = 1
    while (n > 4) {
        n -= 3
        res *= 3
    }
    return result * n
}
const result = integerBreak(10)
console.log('result :>>', result);
